package com.caochenlei.table;

import java.util.HashSet;
import java.util.Set;

public class SymbolTable<Key, Value> {
    private class Node {    //结点类
        public Key key;     //存储键
        public Value value; //存储值
        public Node next;   //下一个

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
        }
    }

    private Node head;      //记录头结点
    private int size;       //键值对个数

    public SymbolTable() {
        this.head = new Node(null, null);
        this.size = 0;
    }

    //获取符号表键值个数
    public int size() {
        return size;
    }

    //判断符号表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //向符号表插入键值对
    public void put(Key key, Value value) {
        //符号表中已经存在了键为key的键值对，那么只需要找到该结点，然后替换值为value即可。
        Node n = head;
        while ((n = n.next) != null) {
            if (n.key.equals(key)) {
                n.value = value;
                return;
            }
        }
        //如果符号表中不存在键为key的键值对，需要创建新的结点，把新结点插入到链表的头部即可。
        Node newFirst = new Node(key, value);
        Node oldFirst = head.next;
        head.next = newFirst;
        newFirst.next = oldFirst;
        size++;
    }

    //删除符号表中键为key的键值对
    public void delete(Key key) {
        Node n = head;
        while (n.next != null) {
            //判断n结点的下一个结点的键是否为key，如果是，就删除该结点
            if (n.next.key.equals(key)) {
                n.next = n.next.next;
                size--;
                return;
            }
            //判断n结点的下一个结点的键是否为key，如果否，就继续向后找
            else {
                n = n.next;
            }
        }
    }

    //获取符号表中键为key的value
    public Value get(Key key) {
        Node n = head;
        while ((n = n.next) != null) {
            if (n.key.equals(key)) {
                return n.value;
            }
        }
        return null;
    }

    //获取符号表中所有key的集合
    public Set<Key> keySet() {
        Set<Key> keySet = new HashSet<>();
        Node n = head;
        while ((n = n.next) != null) {
            keySet.add(n.key);
        }
        return keySet;
    }

    //获取符号表中所有Value的集合
    public Set<Value> valueSet() {
        Set<Value> valueSet = new HashSet<>();
        Node n = head;
        while ((n = n.next) != null) {
            valueSet.add(n.value);
        }
        return valueSet;
    }
}
